package personal.leil.learning.xor;

/**
 * 一道异或（^）的题目
 * <p>
 * 题目描述：
 * 一个数组中有两个数在数组中出现了奇数次，其余的数在数组中出现了偶数次。
 * 问这两个数分别是多少？
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2023-12-29
 */
public class QuestionForXOR {

    /**
     * 问题求解过程
     * <p>
     * 1、将数组中所有的数字进行^运算
     * 2、假设两个数字为a和b，则eor=a^b!=0
     * 3、找出eor在2进制位上最右侧为1的数
     * 4、用sign将原数组分为两组，在sign的为1的二进制位上为0和为1的两组，且a和b一定不在同一组
     * 5、将其中一组进行异或，则可以得到a和b其一
     * </p>
     *
     * @param arr 源数组
     */
    public static void answer(int[] arr) {
        int eor = arr[0];
        for (int i = 1; i < arr.length; i++) {
            eor ^= arr[i];
        }   // 1
        int sign = eor & (~eor + 1);    // 2、3
        int one = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & sign) == 0) {
                one ^= arr[i];
            }
        }   // 4、5
        int anotherOne = eor ^ one;
        System.out.println(String.format("one=%d\r\nanother_one=%d", one, anotherOne));
    }

    /********************* For Test *************************/

    public static void main(String[] args) {
        int[] arr = {3, 3, 4, 4, 4, 5, 6, 6, 7, 6, 6, 7};
        answer(arr);
    }
}
